package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode 39 组合总和
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/14 20:16
 */
public class E39 {
    /*
      nums={2,3,6,7} target=7:

                           2                   3               6           7
                   /     |   |  \          /   |   \           |
                  2      3   6  7         3    6    7          7
               /    \  / | \ x  x       / | \  x    x          x
              2     3 3  6 7           3  6 7
           / | | \    x  x x           x  x x
          2 3 6  7
          x x x  x

       本题题目其实和零钱兑换问题是一模一样的，但是当前题目是球的所有满足条件的集合总数
       而零钱兑换呢，是求的某种形式上的最值问题，例如：求所需最少的硬币数等
     */

    /**
     * 组合总和
     * @param candidates 参与计算的数组
     * @param target 目标值
     * @return 所有可能的组合，可以重复选择数组中的元素
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(0, candidates, result, target, new LinkedList<>());
        return result;
    }

    /**
     * 递归函数，方法: 递归加回溯
     * @param start 当前位置的起始值（最小值）
     * @param candidates 参与计算的数组
     * @param result 结果集
     * @param target 目标值
     * @param currentCombine 当前组合
     */
    private void dfs(int start,
                     int[] candidates,
                     List<List<Integer>> result,
                     int target,
                     LinkedList<Integer> currentCombine) {
        // 递归结束条件：剩余值等于0，说明已经找到一种组合
        if (target == 0){
            result.add(new ArrayList<>(currentCombine));
            return;
        }
        // 尝试当前位置的所有可能
        for (int i = start; i < candidates.length; i++){
            if (target - candidates[i] < 0) continue; // 当这个位置加进去后剩余的都小于0了，没必要尝试后面位置的了，剪枝，也就减少递归，这里的剪枝操作还可以用break;不过需要先对candidates进行排序
            currentCombine.push(candidates[i]); // 当前递归表示第几位，重在位置，而for循环指这个位置有哪些可能
            dfs(i, candidates, result, target - candidates[i], currentCombine); // 递归挑选下一个位置的数
            currentCombine.pop(); // 进入下一轮for循环之前，也就是下一种可能的数，需要回溯
        }
    }
}
